function insertionSort(arr) {
  // 从第二个元素开始，因为第一个元素默认已经排序好
  for (let i = 1; i < arr.length; i++) {
    let current = arr[i]; // 当前要插入的元素
    let j = i - 1; // 已排序部分的最后一个元素的索引

    // 找到当前元素插入的位置
    while (j >= 0 && arr[j] > current) {
      arr[j + 1] = arr[j]; // 移动元素
      j--;
    }

    // 插入当前元素
    arr[j + 1] = current;
  }
  return arr;
}

// 示例
// let arr = [7, 2, 5, 3, 9];
// let _a = [4, 1, 2, 3];
// console.log(insertionSort(_a));
// console.log(insertionSort(arr)); // 输出: [2, 3, 5, 7, 9]

function insertionSort1(arr) {
  // [4,1,2,3]
  for (let i = 1; i < arr.length; i++) {
    // 插入的扑克值
    let current = arr[i];
    // 已排序区域最后一个值
    let j = i - 1;
    while (j >= 0 && arr[j] > current) {
      // 已排序区域当前值大于插入的值 所以已排序区域要右移
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = current; // 此处应插入 current，而不是 arr[i]
  }
  return arr;
}
let _a = [4, 1, 2, 3];
console.log(insertionSort1(_a));
